home *** CD-ROM | disk | FTP | other *** search
/ Cream of the Crop 1 / Cream of the Crop 1.iso / PROGRAM / CUJ9209.ARJ / 1009107A < prev    next >
Text File  |  1992-07-11  |  8KB  |  299 lines
  1. /* --------------------------------------------------------------
  2.  
  3. FUNCTION HELP:
  4.  
  5. -------------------------------------------------------------- */
  6.  
  7. void help(void)
  8. {
  9.     printf("\n   The action codes are:\n");
  10.     printf("\t%c - Produces this help message\n", HELP);
  11.     printf("\t%c - Exit this program\n", EXIT);
  12.     printf("\t%c - Add a new node\n", ADD_NODE);
  13.     printf("\t%c - Remove a node\n", REMOVE_NODE);
  14.     printf("\t%c - Display a node\n", DISPLAY_NODE);
  15.     printf("\t%c - Print all nodes in the tree\n", PRINT_TREE);
  16.     printf("\t%c - Count number of nodes\n", COUNT_NODES);
  17.     printf("\t%c - Find the depth of the tree\n", FIND_DEPTH);
  18. }
  19.  
  20. /* --------------------------------------------------------------
  21.  
  22. FUNCTION REMOVE_NODE: The steps to remove a node from the tree are:
  23.  
  24. A.  Complain if list empty.
  25.  
  26. B.  Get a string from the user.
  27.  
  28. C.  If no such node, complain and get out.
  29.  
  30. D.  If the node to be removed has both left and right children, use 
  31. a 
  32.     different method of deletion than if it has none or only one. 
  33.  
  34.     Deleting a node with two children is much more difficult since 
  35. the 
  36.     node being deleted has two subtrees below it whereas if there 
  37. were 
  38.     no or only one child there would be at most one subtree below. 
  39. Our 
  40.     parent has one pointer currently pointing to us and we cannot 
  41. make 
  42.     that one pointer point to both our children. Removing us requires 
  43.  
  44.     the tree be reorganized on a non-local scale.
  45.  
  46. E.  Free the node being removed along with its string.
  47.  
  48. -------------------------------------------------------------- */
  49.  
  50. void remove_node(Node **pproot_node)
  51. {
  52.     Node *ploc_node;    /* ptr to located node */
  53.     Node *pparent_node;    /* ptr to parent node */
  54.     char string[21];    /* tmp holder for node's string */
  55.  
  56. /*A*/    if (*pproot_node == NULL) {
  57.         printf("\n   List contains no nodes\n");
  58.         return;
  59.     }
  60.  
  61. /*B*/    printf("\n   Enter string: ");
  62.     scanf("%20s", string);
  63.  
  64. /*C*/    ploc_node = find_node(*pproot_node, string, &pparent_node);
  65.     if (ploc_node == NULL) {
  66.  
  67.           printf("\n   No such node exists\n");
  68.         return;
  69.     }
  70.  
  71. /*D*/    if (ploc_node->>pleft_child != NULL
  72.         && ploc_node->>pright_child != NULL) {
  73.         remove_node_1(ploc_node, pparent_node, pproot_node);
  74.     }
  75.     else {
  76.         remove_node_2(ploc_node, pparent_node, pproot_node);
  77.     }
  78.  
  79. /*E*/    free(ploc_node->>pstring);
  80.     put_free_node(ploc_node);
  81.     printf("\n   Node removed\n");
  82. }
  83.  
  84. /* --------------------------------------------------------------
  85.  
  86. FUNCTION REMOVE_NODE_1: The steps to remove a node from the tree if 
  87.  
  88.     that node has two children, are:
  89.  
  90. A.  Find the successor of the node to be deleted and the parent of 
  91.  
  92.     that successor. (The successor is found by an inorder traversal.)
  93.  
  94. B.  Delete the inorder successor node.
  95.  
  96. C.  Replace the node being deleted by its inorder successor as 
  97.     follows: If the current node has a parent,
  98.  
  99. D.  If we are the left child of our parent, replace our parent's left 
  100.  
  101.     child with our successor.
  102.  
  103. E.  Else, we are the right child of our parent, replace our parent's
  104.     right child with our successor.
  105.  
  106. F.  If we are the root (have no parent) make our successor the new 
  107.  
  108.     root.
  109.  
  110. G.  And finally, the successor inherits our two children.
  111.  
  112. -------------------------------------------------------------- */
  113.  
  114. void remove_node_1(Node *ploc_node, Node *pparent_node,
  115.     Node **pproot_node)
  116. {
  117.     Node *ptemp_node = ploc_node->>pright_child;
  118.     Node *psave_node = ploc_node;
  119.     Node *psuc_node;        /* successor node */
  120.     Node *pparent_suc_node;        /* parent successor node */
  121.  
  122. /*A*/    while (ptemp_node->>pleft_child != NULL) {
  123.         psave_node = ptemp_node;
  124.         ptemp_node = ptemp_node->>pleft_child;
  125.     }
  126.  
  127.     psuc_node = ptemp_node;
  128.     pparent_suc_node = psave_node;
  129.  
  130. /*B*/    remove_node_2(psuc_node, pparent_suc_node, pproot_node);
  131.  
  132.  
  133. /*C*/    if (pparent_node != NULL) {
  134. /*D*/        if (ploc_node == pparent_node->>pleft_child) {
  135.             pparent_node->>pleft_child = psuc_node;
  136.         }
  137. /*E*/        else {
  138.             pparent_node->>pright_child = psuc_node;
  139.         }
  140.     }
  141. /*F*/    else {
  142.         *pproot_node = psuc_node;
  143.     }
  144.  
  145. /*G*/    psuc_node->>pleft_child = ploc_node->>pleft_child;
  146.     psuc_node->>pright_child = ploc_node->>pright_child;
  147. }
  148.  
  149. /* --------------------------------------------------------------
  150.  
  151. FUNCTION REMOVE_NODE_2: The steps to remove a node from the tree if 
  152.  
  153.     that node has none or only one child, are:
  154.  
  155. A.  If node to be deleted has no children we have nothing to keep 
  156.  
  157.     track of.
  158.  
  159. B.  Else, if it has only a left child, keep track of the path to that.
  160.  
  161. C.  Else, it has only a right child so keep track of the path to that.
  162.  
  163. D.  If the current node has a parent, and the current node is the 
  164. left 
  165.     child of that parent, make the parent inherit the child of the
  166.     node to be deleted. (If there is no child, the parent inherits 
  167.  
  168.     NULL.)
  169.  
  170. E.  If the current node has a parent, and the current node is the 
  171.  
  172.     right child of that parent, make the parent inherit the child 
  173. of
  174.     the node to be deleted. (If there is no child, the parent inherits 
  175.  
  176.     NULL.)
  177.  
  178. F.  Otherwise, if there is no parent, we are deleting the root node 
  179. so 
  180.     make the new root the child of the node being deleted.  (If there
  181.     is no child, the root becomes NULL.)
  182.  
  183. -------------------------------------------------------------- */
  184.  
  185. void remove_node_2(Node *ploc_node, Node *pparent_node,
  186.     Node **pproot_node)
  187. {
  188.     Node *pchild_node;
  189.  
  190. /*A*/    if (ploc_node->>pleft_child == NULL
  191.         && ploc_node->>pright_child == NULL) {
  192.             pchild_node = NULL;
  193.     }
  194. /*B*/    else if (ploc_node->>pleft_child != NULL) {
  195.             pchild_node = ploc_node->>pleft_child;
  196.     }
  197. /*C*/    else {
  198.             pchild_node = ploc_node->>pright_child;
  199.     }
  200.  
  201.  = 
  202. /*D*/    if (pparent_node != NULL) {
  203.         if (ploc_node == pparent_node->>pleft_child) {
  204.             pparent_node->>pleft_child = pchild_node;
  205.         }
  206. /*E*/        else {
  207.             pparent_node->>pright_child = pchild_node;
  208.         }
  209.     }
  210. /*F*/    else {
  211.         *pproot_node = pchild_node;
  212.     }
  213. }
  214.  
  215. /* ----------------------------------------------------------- */
  216.  
  217. /* stack management code */
  218.  
  219. /* ----------------------------------------------------------- */
  220.  
  221. #define STACK_SIZE 100
  222.  
  223. static Node *stack[STACK_SIZE];
  224.  
  225. static size_t stack_ptr = 0;
  226.  
  227. void push(Node *value)
  228. {
  229.     if (stack_ptr == STACK_SIZE)
  230.         printf("Stack is full\n");
  231.     else
  232.         stack[stack_ptr++] = value;
  233. }
  234.  
  235. Node *pop(void)
  236. {
  237.     if (stack_ptr == 0) {
  238.         printf("Stack is empty\n");
  239.         return 0;
  240.     }
  241.  
  242.     return stack[--stack_ptr];
  243. }
  244.  
  245. static Node *pfree_node = NULL;    /* next free node */
  246.  
  247. /* ----------------------------------------------------------- */
  248.  
  249. /* free node list management code */
  250.  
  251. /* --------------------------------------------------------------
  252.  
  253. FUNCTION GET_FREE_NODE: The steps to get a node from the free node
  254.     list are:
  255.  
  256. A.  If the free node list is empty, get memory for a new node and 
  257.  
  258.     return its address. (Allocation failure is handled by caller.)
  259.  
  260. B.  Else remove the first node from the free list and use that.
  261.  
  262.  
  263. -------------------------------------------------------------- 
  264. */
  265.  
  266. Node *get_free_node(void)
  267. {
  268.     Node *pnew_node;
  269.  
  270. /*A*/    if (pfree_node == NULL) {
  271.         pnew_node = malloc(sizeof(Node));
  272.     }
  273. /*B*/    else {
  274.         pnew_node = pfree_node;
  275.         pfree_node = pfree_node->>pleft_child;
  276.     }
  277.  
  278.     return pnew_node;
  279. }
  280.  
  281. /* --------------------------------------------------------------
  282.  
  283. FUNCTION PUT_FREE_NODE: The steps to release an active node and add
  284.     it to the front of the free list are:
  285.  
  286. A.  Insert the node at the start of the free node list.
  287.  
  288. -------------------------------------------------------------- */
  289.  
  290. void put_free_node(Node *pnode)
  291. {
  292. /*A*/    pnode->>pleft_child = pfree_node;
  293.     pfree_node = pnode;
  294. }
  295.  
  296. /* ----------------------------------------------------------- */
  297.  
  298.  
  299.